{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Strobogrammatic Number II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #array #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #数组 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findStrobogrammatic"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #中心对称数 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数&nbsp;<code>n</code>&nbsp;，返回所有长度为&nbsp;<code>n</code>&nbsp;的 <strong>中心对称数</strong>&nbsp;。你可以以 <strong>任何顺序</strong> 返回答案。</p>\n",
    "\n",
    "<p><strong>中心对称数&nbsp;</strong>是一个数字在旋转了&nbsp;<code>180</code> 度之后看起来依旧相同的数字（或者上下颠倒地看）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 2\n",
    "<b>输出：</b>[\"11\",\"69\",\"88\",\"96\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 1\n",
    "<b>输出：</b>[\"0\",\"1\",\"8\"]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 14</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [strobogrammatic-number-ii](https://leetcode.cn/problems/strobogrammatic-number-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [strobogrammatic-number-ii](https://leetcode.cn/problems/strobogrammatic-number-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2', '1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result = defaultdict(list)\n",
    "    \n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "#         1-1, 6-9, 8-8, 0-0\n",
    "        if n in self.result:\n",
    "            return self.result.get(n)\n",
    "        \n",
    "        if n == 0:\n",
    "            return []\n",
    "        if n == 1:\n",
    "            return [\"0\", \"1\", \"8\"]\n",
    "        if n == 2:\n",
    "            return [\"11\",\"69\",\"88\",\"96\"]\n",
    "        \n",
    "        if n % 2 == 0:\n",
    "            item_list = self.findStrobogrammatic(n-2)\n",
    "            for item in item_list:\n",
    "                for num in ['11', '69', '88', '96', '00']:\n",
    "                    self.result[n].append(item[:(n-2)//2] + num + item[(n-2)//2:])\n",
    "            return self.result[n]\n",
    "        if n % 2 == 1:\n",
    "            item_list = self.findStrobogrammatic(n-1)\n",
    "            for item in item_list:\n",
    "                for num in ['1', '0', '8']:\n",
    "                    self.result[n].append(item[:(n-1)//2] + num + item[(n-1)//2:])\n",
    "            return self.result[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        #018 #01869\n",
    "        #mid 018\n",
    "        #mirror 01869\n",
    "        d={\"0\":\"0\",\"1\":\"1\",\"8\":\"8\",\"6\":\"9\",\"9\":\"6\"}\n",
    "        if n==1:\n",
    "            return [\"0\",\"1\",\"8\"]\n",
    "      \n",
    "        ans=[]\n",
    "        dfs=[\"\"]\n",
    "        if n%2==1:\n",
    "            dfs=[\"0\",\"1\",\"8\"]\n",
    "        while dfs:\n",
    "            cur=dfs.pop()\n",
    "            if n-len(cur)==2:\n",
    "                ans+=[\"1\"+cur+\"1\",\"8\"+cur+\"8\",\"6\"+cur+\"9\",\"9\"+cur+\"6\"]\n",
    "            else:\n",
    "                dfs+=[\"0\"+cur+\"0\",\"1\"+cur+\"1\",\"8\"+cur+\"8\",\"6\"+cur+\"9\",\"9\"+cur+\"6\"] \n",
    "               \n",
    "        return ans\n",
    "       \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "import copy\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        stack = deque()\n",
    "        chenmap = {6 : 9, 9 : 6, 8 : 8, 1 : 1, 0 : 0}\n",
    "        k = n // 2\n",
    "        self.huisu(k, \"\", stack, chenmap, n % 2)\n",
    "        return self.res\n",
    "    def huisu(self, k, zuhe, stack, chenmap, ji):\n",
    "        if k == 0:\n",
    "            zuhe_ls = []\n",
    "            if ji:\n",
    "                for num in [0, 1, 8]:\n",
    "                    zuhe_ls.append(zuhe[:] + str(num))\n",
    "            else:\n",
    "                zuhe_ls.append(zuhe[:])\n",
    "            after_s = \"\"\n",
    "            stack_copy = copy.deepcopy(stack)\n",
    "            while stack_copy:\n",
    "                after_s += str(chenmap[stack_copy.pop()])\n",
    "            for s in zuhe_ls:\n",
    "                self.res.append(s + after_s)\n",
    "            return        \n",
    "        for num in chenmap.keys():\n",
    "            if num == 0 and zuhe == \"\":\n",
    "                continue\n",
    "            stack.append(num)\n",
    "            zuhe += str(num)\n",
    "            self.huisu(k - 1, zuhe, stack, chenmap, ji)\n",
    "            zuhe = zuhe[:-1]\n",
    "            stack.pop()\n",
    "        return  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        return list(s for s in self.generator(n) if not s.startswith('0') or s == '0')\n",
    "    def generator(self, n):\n",
    "        if n == 1:\n",
    "            yield '0'\n",
    "            yield '1'\n",
    "            yield '8'\n",
    "            return\n",
    "        if n == 0:\n",
    "            yield ''\n",
    "            return\n",
    "        for s in self.generator(n-2):\n",
    "            yield '0' + s + '0'\n",
    "            yield '1' + s + '1'\n",
    "            yield '6' + s + '9'\n",
    "            yield '8' + s + '8'\n",
    "            yield '9' + s + '6'\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        store = {\n",
    "            '0': '0',\n",
    "            '1': '1',\n",
    "            '6': '9',\n",
    "            '8': '8',\n",
    "            '9': '6'\n",
    "        }\n",
    "        result = []\n",
    "        self.recurse(0, n, [], store, result)\n",
    "        return result\n",
    "\n",
    "    def help(self, string, store):\n",
    "        return [store[char] for char in string][::-1]\n",
    "\n",
    "    def recurse(self, start, end, string, store, result):\n",
    "        if start > (end + 1) // 2:\n",
    "            return \n",
    "        if (start == (end + 1) // 2) and (string[0] != '0' or end == 1):\n",
    "            if end % 2:\n",
    "                result.append(''.join(string + self.help(string[:-1], store)))\n",
    "            else:\n",
    "                result.append(''.join(string + self.help(string, store)))\n",
    "            return \n",
    "        for k in store.keys():\n",
    "            if end % 2 and start == end // 2 and k not in ('0', '1', '8'):\n",
    "                continue\n",
    "            string.append(k)\n",
    "            self.recurse(start + 1, end, string, store, result)\n",
    "            string.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        #018 #01869\n",
    "        #mid 018\n",
    "        #mirror 01869\n",
    "        d={\"0\":\"0\",\"1\":\"1\",\"8\":\"8\",\"6\":\"9\",\"9\":\"6\"}\n",
    "        h=n//2\n",
    "        \n",
    "        if h>0:\n",
    "            ans=[]\n",
    "            dfs=[\"1\",\"8\",\"6\",\"9\"]\n",
    "            while dfs:\n",
    "                cur=dfs.pop()\n",
    "                if len(cur)<h:\n",
    "                    dfs+=[cur+\"0\",cur+\"1\",cur+\"8\",cur+\"6\",cur+\"9\"]\n",
    "                else:\n",
    "                   \n",
    "                    back=list(cur[::-1])\n",
    "                    for i in range(h):\n",
    "                        back[i]=d[back[i]]\n",
    "                    bk=\"\".join(back)\n",
    "                    if n%2==1:\n",
    "                        ans+=[cur+\"0\"+bk,cur+\"1\"+bk,cur+\"8\"+bk]\n",
    "                    else:\n",
    "                        ans+=[cur+bk]\n",
    "            return ans\n",
    "        else:\n",
    "            return [\"0\",\"1\",\"8\"]\n",
    "\n",
    "        # m=n//2\n",
    "        # res=4*5**(m-1)\n",
    "        # if n%2==1:\n",
    "        #     res*=3\n",
    "        # return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        self.dic = {\"0\": \"0\", \"1\": \"1\", \"6\": \"9\", \"8\": \"8\", \"9\": \"6\"}\n",
    "        self.ans = []\n",
    "        self.backtrace(n, [\"\"] * n, n // 2, 0)\n",
    "        return self.ans\n",
    "\n",
    "    def backtrace(self, n, lst, limit, idx):\n",
    "        if idx == limit:\n",
    "            if n % 2 == 0:\n",
    "                self.ans.append(\"\".join(lst))\n",
    "            else:\n",
    "                for num in \"018\":\n",
    "                    lst[limit] = num\n",
    "                    self.ans.append(\"\".join(lst))\n",
    "            return\n",
    "        if idx == 0:\n",
    "            for num in \"1689\":\n",
    "                lst[idx] = num\n",
    "                lst[n - 1 - idx] = self.dic[num]\n",
    "                self.backtrace(n, lst, limit, idx + 1)\n",
    "        else:\n",
    "            for num in \"01689\":\n",
    "                lst[idx] = num\n",
    "                lst[n - 1 - idx] = self.dic[num]\n",
    "                self.backtrace(n, lst, limit, idx + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        if n < 1:\n",
    "            return []\n",
    "\n",
    "        stro_numbers = {\n",
    "            0: 0,\n",
    "            1: 1,\n",
    "            6: 9,\n",
    "            8: 8,\n",
    "            9: 6,\n",
    "        }\n",
    "\n",
    "        res = []\n",
    "        if n % 2 == 0:\n",
    "            self._build_str(n, \"\", stro_numbers, res)\n",
    "        else:\n",
    "            for center in [\"0\", \"1\", \"8\"]:\n",
    "                self._build_str(n, center, stro_numbers, res)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "    def _build_str(self, n, cur_str, stro_numbers, res):\n",
    "        if len(cur_str) == n:\n",
    "            if n != 1 and cur_str.startswith(\"0\"):\n",
    "                return\n",
    "            \n",
    "            res.append(cur_str)\n",
    "            return\n",
    "        \n",
    "\n",
    "        for k, v in stro_numbers.items():\n",
    "\n",
    "            self._build_str(n, str(k) + cur_str + str(v), stro_numbers, res)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        # res = []\n",
    "        # nums = [str(num) for num in range(10**(n-1), 10**n) if num%(10**(n-1)) in ['1','6','8','9']]\n",
    "        # print(nums)\n",
    "        # if n ==1: return ['0','1','8']\n",
    "        # if n%2 == 0:\n",
    "        #     for num in nums:\n",
    "        #         add = True\n",
    "        #         for i in range(int(n/2)):\n",
    "        #             if i == 0:\n",
    "        #                 if num[i] == num[n-i-1] and num[i] in ['1','8']:\n",
    "        #                     continue\n",
    "        #                 elif (num[i] == '9' and num[n-i-1] =='6') or (num[i] == '6' and num[n-i-1] =='9'): \n",
    "        #                     continue\n",
    "        #                 else:\n",
    "        #                     add = False\n",
    "        #             else:\n",
    "        #                 if num[i] == num[n-i-1] and num[i] in ['0', '1','8']:\n",
    "        #                     continue\n",
    "        #                 elif (num[i] == '9' and num[n-i-1] =='6') or (num[i] == '6' and num[n-i-1] =='9'): \n",
    "        #                     continue\n",
    "        #                 else:\n",
    "        #                     add = False\n",
    "        #         if add:\n",
    "        #             res.append(num)\n",
    "        # else:\n",
    "        #     for num in nums:\n",
    "        #         add = True               \n",
    "        #         for i in range(int((n-1)/2)):\n",
    "        #             if i == 0:\n",
    "        #                 if num[i] == num[n-i-1] and num[i] in ['1','8']:\n",
    "        #                     continue\n",
    "        #                 elif (num[i] == '9' and num[n-i-1] =='6') or (num[i] == '6' and num[n-i-1] =='9'): \n",
    "        #                     continue\n",
    "        #                 else:\n",
    "        #                     add = False\n",
    "        #             else:\n",
    "        #                 if num[i] == num[n-i-1] and num[i] in ['0', '1','8']:\n",
    "        #                     continue\n",
    "        #                 elif (num[i] == '9' and num[n-i-1] =='6') or (num[i] == '6' and num[n-i-1] =='9'): \n",
    "        #                     continue\n",
    "        #                 else:\n",
    "        #                     add = False\n",
    "        #         if num[int((n-1)/2)] not in ['0','1','8']: \n",
    "        #             add = False\n",
    "        #         if add:\n",
    "        #             res.append(num)\n",
    "        # return res\n",
    "        #chaoshi\n",
    "        pairs = [['1','1'],['8','8'],['6','9'],['9','6']]\n",
    "        def fun(x):\n",
    "            if x == 0: return [\"\"]\n",
    "            elif x == 1:\n",
    "                return ['0','1','8']\n",
    "            res = []\n",
    "            for num in fun(x-2):\n",
    "                for a, b in pairs:\n",
    "                    res.append(a+num+b)\n",
    "                if x!=n:\n",
    "                    res.append('0'+num+'0')\n",
    "            return res\n",
    "        return fun(n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def build_strobogrammatic(self, context: str, results: set[str], depth: int, max_len: int, rotate_dict: dict):\n",
    "      for k in rotate_dict:\n",
    "        if depth == max_len and k == '0':\n",
    "          continue\n",
    "        if depth == 1:\n",
    "          results.append(context + k)\n",
    "        else:\n",
    "          self.build_strobogrammatic(context + k, results, depth - 1, max_len, rotate_dict)\n",
    "\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "      results = []\n",
    "      if n == 1:\n",
    "        return ['1', '8', '0']\n",
    "      \n",
    "      rotate_dict = {\n",
    "        \"1\": \"1\",\n",
    "        \"6\": \"9\",\n",
    "        \"8\": \"8\",\n",
    "        \"9\": \"6\",\n",
    "        \"0\": \"0\"\n",
    "      }\n",
    "\n",
    "      center = -1\n",
    "      if int(n / 2) != n / 2:\n",
    "        center = int(n / 2) + 1\n",
    "\n",
    "      left_length = int(n / 2)\n",
    "\n",
    "      # result_length = left_length * len(rotate_dict) - 1\n",
    "      \n",
    "      self.build_strobogrammatic(\"\", results, left_length, left_length, rotate_dict)\n",
    "\n",
    "      final_results = []\n",
    "      for left_side in results:\n",
    "        right_side = \"\"\n",
    "        for i in left_side:\n",
    "          right_side = rotate_dict[i] + right_side\n",
    "        \n",
    "        if center != -1:\n",
    "          for k in ['1', '8', '0']:\n",
    "            final_results.append(left_side + k + right_side)\n",
    "        else:\n",
    "          final_results.append(left_side + right_side)\n",
    "      \n",
    "      return final_results\n",
    "      \n",
    "\n",
    "            \n",
    "      \n",
    "      \n",
    "\n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        pairs = [['1', '1'], ['8', '8'], ['6', '9'],['9','6']]\n",
    "\n",
    "        def fun(x):\n",
    "            if x == 0:\n",
    "                return [\"\"]\n",
    "            elif x == 1:\n",
    "                return [\"0\", \"1\", \"8\"]\n",
    "            res = []\n",
    "            for num in fun(x - 2):\n",
    "                for a, b in pairs:\n",
    "                    res.append(a + num + b)\n",
    "                \n",
    "                if x != n:\n",
    "                    res.append(\"0\" + num + \"0\")\n",
    "            return res \n",
    "        return fun(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "\n",
    "        pairs = [['1','1'],['8','8'],['6','9'],['9','6']]\n",
    "\n",
    "        def fun(x):\n",
    "            if x == 0:\n",
    "                return [\"\"]\n",
    "            elif x == 1:\n",
    "                return [\"0\", \"1\", \"8\"]\n",
    "            res = []\n",
    "            for num in fun(x - 2):\n",
    "                for a,b in pairs:\n",
    "                    res.append(a + num + b)\n",
    "                    \n",
    "                if x != n:\n",
    "                    res.append(\"0\" + num + \"0\")\n",
    "            return res\n",
    "        #print(fun(n))\n",
    "        return fun(n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        pairs = [['1','1'],['8','8'],['6','9'],['9','6']]\n",
    "\n",
    "        def dfs(x):\n",
    "            if x == 0: return [\"\"]\n",
    "            elif x == 1: return ['0', '1', '8']\n",
    "            ans = []\n",
    "            for num in dfs(x - 2):\n",
    "                for a, b in pairs:\n",
    "                    ans.append(a + num + b)\n",
    "\n",
    "                if x != n:\n",
    "                    ans.append('0' + num + '0')\n",
    "            return ans\n",
    "\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "\n",
    "        pairs = [['1','1'],['8','8'],['6','9'],['9','6']]\n",
    "\n",
    "        def fun(x):\n",
    "            if x == 0:\n",
    "                return [\"\"]\n",
    "            elif x == 1:\n",
    "                return [\"0\", \"1\", \"8\"]\n",
    "            res = []\n",
    "            for num in fun(x - 2):\n",
    "                for a,b in pairs:\n",
    "                    res.append(a + num + b)\n",
    "                    \n",
    "                if x != n:\n",
    "                    res.append(\"0\" + num + \"0\")\n",
    "            return res\n",
    "        #print(fun(n))\n",
    "        return fun(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        pairs = [['1','1'],['8','8'],['6','9'],['9','6']]\n",
    "\n",
    "        def fun(x):\n",
    "            if x == 0:\n",
    "                return [\"\"]\n",
    "            elif x == 1:\n",
    "                return [\"0\", \"1\", \"8\"]\n",
    "            res = []\n",
    "            for num in fun(x - 2):\n",
    "                for a,b in pairs:\n",
    "                    res.append(a + num + b)\n",
    "                    \n",
    "                if x != n:\n",
    "                    res.append(\"0\" + num + \"0\")\n",
    "            return res\n",
    "\n",
    "        return fun(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    self_center = [\"0\", \"1\", \"8\"]\n",
    "    dual_center = [\"6\", \"9\"]\n",
    "\n",
    "    \n",
    "    \n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "\n",
    "        dual_map = {\n",
    "                    \"1\": \"1\", \"0\": \"0\", \"8\": \"8\", \"6\": \"9\", \"9\": \"6\"\n",
    "                    }\n",
    "        \n",
    "        def dfs(k, word, ret):\n",
    "            if k == 0:\n",
    "                ret.append(word)\n",
    "                return\n",
    "            for v in dual_map.keys():\n",
    "                dfs(k - 2, v + word + dual_map[v], ret)\n",
    "        \n",
    "        ret = []\n",
    "        if n % 2 == 0:\n",
    "            dfs(n, \"\", ret)\n",
    "        else:\n",
    "            for k in dual_map.keys():\n",
    "                if k == dual_map[k]:\n",
    "                    dfs(n-1, k, ret)\n",
    "        \n",
    "        return [_ for _ in ret if len(_) == 1 or  _[0]!='0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def help(self, n: int, depth: int) -> List[str]:\n",
    "        if n == 1:\n",
    "            return [\"0\", \"1\", \"8\"]\n",
    "        if n == 2:\n",
    "            ret = [\"11\",\"69\",\"88\",\"96\"]\n",
    "            if depth == 0:\n",
    "                return ret\n",
    "            ret.append(\"00\")\n",
    "            return ret\n",
    "        ret = self.help(n-2, depth+1)\n",
    "        ans = []\n",
    "        for val in ret:\n",
    "            ans.append(\"1\" + val + \"1\")\n",
    "            ans.append(\"6\" + val + \"9\")\n",
    "            ans.append(\"8\" + val + \"8\")\n",
    "            ans.append(\"9\" + val + \"6\")\n",
    "            if depth > 0:\n",
    "                ans.append(\"0\" + val + \"0\")\n",
    "        return ans\n",
    "\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        return self.help(n, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "\n",
    "        pairs = [['1','1'],['8','8'],['6','9'],['9','6']]\n",
    "\n",
    "        def fun(x):\n",
    "            if x == 0:\n",
    "                return [\"\"]\n",
    "            elif x == 1:\n",
    "                return [\"0\", \"1\", \"8\"]\n",
    "            res = []\n",
    "            for num in fun(x - 2):\n",
    "                for a,b in pairs:\n",
    "                    res.append(a + num + b)\n",
    "                    \n",
    "                if x != n:\n",
    "                    res.append(\"0\" + num + \"0\")\n",
    "            return res\n",
    "\n",
    "        return fun(n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        # # 1-1 6-9 8-8 0-0\n",
    "        # # \n",
    "        # # 先构建再去重\n",
    "        # res = []\n",
    "        \n",
    "        # 回溯算法\n",
    "        def generate_helper(m, n):\n",
    "            if m == 0:\n",
    "                return ['']\n",
    "            if m == 1:\n",
    "                return ['0', '1', '8']\n",
    "\n",
    "            prev = generate_helper(m - 2, n)\n",
    "            result = []\n",
    "            for s in prev:\n",
    "                if m != n:\n",
    "                    result.append('0' + s + '0')\n",
    "                result.append('1' + s + '1')\n",
    "                result.append('6' + s + '9')\n",
    "                result.append('8' + s + '8')\n",
    "                result.append('9' + s + '6')\n",
    "            return result\n",
    "\n",
    "        return generate_helper(n, n)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        dict={'1':'1','6':'9','9':'6','8':'8'}\n",
    "        def fun(x):\n",
    "            if x==0:\n",
    "                return ['']\n",
    "            if x==1:\n",
    "                return ['0','1','8']\n",
    "            ans=[]\n",
    "            for num in fun(x-2):\n",
    "                for key,value in dict.items():\n",
    "                    ans.append(key+num+value)\n",
    "                if x!=n:\n",
    "                    ans.append('0'+num+'0')\n",
    "            return ans\n",
    "        return fun(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:  \n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:  \n",
    "        ab = [['1','1'],['8','8'],['6','9'],['9','6']]\n",
    "        def fun(x):  \n",
    "            if x == 0:  \n",
    "                return ['']  \n",
    "            elif x ==1:  \n",
    "                return['0','1','8']  \n",
    "            res = []  \n",
    "            for i in fun(x-2):  \n",
    "                for a,b in ab:  \n",
    "                    res.append(a+i+b)  \n",
    "                if x!=n:  \n",
    "                    res.append('0'+i+'0')  \n",
    "            return res\n",
    "        \n",
    "        return fun(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        pairs = [['1', '1'], ['8', '8'], ['6', '9'], ['9', '6']]\n",
    "        def dfs(cur):\n",
    "            if cur == 0:\n",
    "                return ['']\n",
    "            elif cur == 1:\n",
    "                return ['0', '1', '8']\n",
    "            \n",
    "            ans = []\n",
    "            for num in dfs(cur - 2):\n",
    "                for l, r in pairs:\n",
    "                    ans.append(l+num+r)\n",
    "                if cur != n:\n",
    "                    ans.append('0' + num + '0')\n",
    "            return ans\n",
    "        \n",
    "        return dfs(n)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        def helper(n):\n",
    "            if n == 1:\n",
    "                return ['0', '1', '8']\n",
    "            elif n == 2:\n",
    "                return [\"00\", \"11\",\"69\",\"88\",\"96\"]\n",
    "            else:\n",
    "                return [k1 + item + k2 for k1, k2 in zip(['0', '1', '6', '8', '9'], ['0', '1', '9', '8', '6']) for item in helper(n-2)]\n",
    "\n",
    "        if n == 1:\n",
    "            return ['0', '1', '8']\n",
    "        elif n == 2:\n",
    "            return [\"11\",\"69\",\"88\",\"96\"]\n",
    "        else:\n",
    "            return [k1 + item + k2 for k1, k2 in zip(['1', '6', '8', '9'], ['1', '9', '8', '6']) for item in helper(n-2)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        pairs = [('1', '1'), ('8', '8'), ('6', '9'), ('9', '6')]\n",
    "        def back_tracking(x):\n",
    "            if x == 0:\n",
    "                return [\"\"]\n",
    "            if x == 1:\n",
    "                return ['0', '1', '8']\n",
    "            \n",
    "            ans = []\n",
    "            for num in back_tracking(x - 2):\n",
    "                for a, b in pairs:\n",
    "                    ans.append(a + num + b)\n",
    "                if x != n:\n",
    "                    ans.append('0' + num + '0')\n",
    "            return ans\n",
    "        return back_tracking(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        if n == 1:\n",
    "            return ['0', '1', '8']\n",
    "        arr, t = ['1689'] + ['01689'] * (n//2-1), str.maketrans('69', '96')\n",
    "        n & 1 and arr.append('018')\n",
    "        tmp = [*map(''.join, product(*arr))]\n",
    "        return [x + x[::-1][n&1:].translate(t) for x in tmp]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    _PAIRS = [(\"1\", \"1\"), (\"6\", \"9\"), (\"8\", \"8\"), (\"9\", \"6\")]\n",
    "\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        \n",
    "        def _dfs(cur_n):\n",
    "            if cur_n == 0:\n",
    "                return [\"\"]\n",
    "            if cur_n == 1:\n",
    "                return [\"1\", \"8\", \"0\"]\n",
    "\n",
    "            result = []\n",
    "\n",
    "            for num in _dfs(cur_n - 2):\n",
    "                for l, r in self._PAIRS:\n",
    "                    result.append(l + num + r)\n",
    "                \n",
    "                if cur_n != n:\n",
    "                    result.append(\"0\" + num + \"0\")\n",
    "            return result\n",
    "        return _dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        pairs = [['1','1'],['8','8'],['6','9'],['9','6']]\n",
    "\n",
    "        def dfs(x):\n",
    "            if x == 0:\n",
    "                return [\"\"]\n",
    "            elif x == 1:\n",
    "                return [\"0\", \"1\", \"8\"]\n",
    "\n",
    "            ans = []\n",
    "\n",
    "            for num in dfs(x - 2):\n",
    "                for a, b in pairs:\n",
    "                    ans.append(a + num + b)\n",
    "                if x != n:\n",
    "                    ans.append(\"0\" + num + \"0\")\n",
    "            return ans\n",
    "\n",
    "        return dfs(n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "\n",
    "        reverse_pairs = [\n",
    "            ['0', '0'], ['1', '1'], ['8', '8'], ['6', '9'], ['9', '6']\n",
    "        ]\n",
    "\n",
    "        def generate(n, final_len) -> List[str]:\n",
    "            if n == 1:\n",
    "                return ['1', '8', '0']\n",
    "            elif n == 0:\n",
    "                return ['']\n",
    "            \n",
    "            pre_pairs = generate(n-2, final_len)\n",
    "            cur_pairs = []\n",
    "            for pre in pre_pairs:\n",
    "                for rev in reverse_pairs:\n",
    "                    if rev[0] != '0' or n != final_len:\n",
    "                        cur_pairs.append(rev[0] + pre + rev[1])\n",
    "            \n",
    "            return cur_pairs\n",
    "        \n",
    "        return generate(n, n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        pairs = [['1','1'],['8','8'],['6','9'],['9','6']]\n",
    "        \n",
    "        def dfs(x):\n",
    "            if x == 0:\n",
    "                return [\"\"]\n",
    "            if x == 1:\n",
    "                return [\"0\", \"1\", \"8\"]\n",
    "            \n",
    "            res = []\n",
    "\n",
    "            for num in dfs(x-2):\n",
    "                for a, b in pairs:\n",
    "                    res.append(a + num + b)\n",
    "                \n",
    "                if x != n:\n",
    "                    res. append('0' + num + '0')\n",
    "            return res\n",
    "        \n",
    "        return dfs(n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        pairs = [['1', '1'], ['8', '8'], ['6', '9'], ['9', '6']]\n",
    "        def dfs(x):\n",
    "            if x == 0:\n",
    "                return ['']\n",
    "            elif x == 1:\n",
    "                return ['0', '1', '8']\n",
    "            res = []\n",
    "            for y in dfs(x - 2):\n",
    "                for a, b in pairs:\n",
    "                    res.append(a + y + b)\n",
    "                \n",
    "                if x != n:\n",
    "                    res.append('0' + y + '0')\n",
    "            return res\n",
    "        return dfs(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        reversible_pairs = [\n",
    "            ['0', '0'], ['1', '1'], \n",
    "            ['6', '9'], ['8', '8'], ['9', '6']\n",
    "        ]\n",
    "\n",
    "        def generate_strobo_numbers(n, final_length):\n",
    "            if n == 0:\n",
    "                # 0 位对称数是一个空字符串。\n",
    "                return [\"\"]\n",
    "\n",
    "            if n == 1:\n",
    "                # 1 位对称数\n",
    "                return [\"0\", \"1\", \"8\"]\n",
    "\n",
    "            prev_strobo_nums = generate_strobo_numbers(n - 2, final_length)\n",
    "            curr_strobo_nums = []\n",
    "\n",
    "            for prev_strobo_num in prev_strobo_nums:\n",
    "                for pair in reversible_pairs:\n",
    "                    if pair[0] != '0' or n != final_length:\n",
    "                        curr_strobo_nums.append(pair[0] + prev_strobo_num + pair[1])\n",
    "\n",
    "            return curr_strobo_nums\n",
    "            \n",
    "        return generate_strobo_numbers(n, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        # 递归：N-2位对称数和开头结尾的可逆数位，从底至顶上溯\n",
    "        reversible_pairs = [\n",
    "            ['0', '0'], ['1', '1'],\n",
    "            [\"6\", \"9\"], [\"8\", \"8\"], [\"9\", \"6\"]\n",
    "        ]\n",
    "        def f(n, final_length):\n",
    "            if n == 0:\n",
    "                return [\"\"]\n",
    "            if n == 1:\n",
    "                return [\"0\", \"1\", \"8\"]\n",
    "            # 一步步组装，先假装组装了n-2了\n",
    "            pre_nums = f(n-2, final_length)\n",
    "            cur_nums = []\n",
    "            for pre_num in pre_nums:\n",
    "                for pair in reversible_pairs:\n",
    "                    if pair[0] != '0' or n != final_length:\n",
    "                        cur_nums.append(pair[0] + pre_num + pair[1])\n",
    "            return cur_nums\n",
    "        return f(n, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        \n",
    "        pairs = [['1','1'],['6','9'],['9','6'],['8','8']]\n",
    "        def fun(x):\n",
    "            if x == 0:\n",
    "                result = [\"\"]\n",
    "                return result\n",
    "            elif x == 1:\n",
    "                result = [\"0\",\"1\",\"8\"]\n",
    "                return result\n",
    "            #elif x == 2:\n",
    "                #result = [\"11\",\"69\",\"96\",\"88\"]\n",
    "                #return result\n",
    "            else:\n",
    "                result = []\n",
    "\n",
    "                for key in fun(x-2):\n",
    "\n",
    "                    for pair in pairs:\n",
    "                        item = pair[0] + key + pair[1]\n",
    "                        result.append(item)\n",
    "                    if x!= n:\n",
    "                        item = '0' + key + '0'\n",
    "                        result.append(item)\n",
    "                    \n",
    "                return result\n",
    "                \n",
    "  \n",
    "        return fun(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        pairs = [['1','1'],['8','8'],['6','9'],['9','6']]\n",
    "\n",
    "        def fun(x):\n",
    "            if x == 0:\n",
    "                return [\"\"]\n",
    "            elif x == 1:\n",
    "                return [\"0\", \"1\", \"8\"]\n",
    "            res = []\n",
    "            for num in fun(x - 2):\n",
    "                for a,b in pairs:\n",
    "                    res.append(a + num + b)\n",
    "                    \n",
    "                if x != n:\n",
    "                    res.append(\"0\" + num + \"0\")\n",
    "            return res\n",
    "\n",
    "        return fun(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        chlist1 = ['1', '8', '6', '9']\n",
    "        chlist2 = ['1', '8', '9', '6']\n",
    "        chlist3 = ['1', '8', '0']\n",
    "        chlist4 = ['1', '8', '6', '9', '0']\n",
    "        chlist5 = ['1', '8', '9', '6', '0']\n",
    "        m = n // 2\n",
    "        if n % 2 == 1:    \n",
    "            ans = chlist3.copy()\n",
    "        else:\n",
    "            ans = ['']\n",
    "        for i in range(m):\n",
    "            if i == (m - 1):\n",
    "                left, right = chlist1, chlist2\n",
    "            else:\n",
    "                left, right = chlist4, chlist5\n",
    "            temp = []\n",
    "            for s in ans:\n",
    "                for j in range(len(left)):\n",
    "                    temp.append(left[j] + s + right[j])\n",
    "            ans = temp\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        n1=['0','1','8']\n",
    "        n2=[\"11\",\"69\",\"88\",\"96\"]\n",
    "        n20=n2[:]\n",
    "        n20.append('00')\n",
    "        n21=n20[:]\n",
    "        if n==1:\n",
    "            return n1\n",
    "        elif n==2:\n",
    "            return n2\n",
    "        res=[]\n",
    "        # n为奇数\n",
    "        if n%2:\n",
    "            for i in range(n//2):\n",
    "                if i != n//2-1:\n",
    "                    for s1 in n1:\n",
    "                        for s2 in n21:\n",
    "                            res.append(s2[0]+s1+s2[1])\n",
    "                    n1=res[:]\n",
    "                    res=[]\n",
    "                else:\n",
    "                    for s1 in n1:\n",
    "                        for s2 in n2:\n",
    "                            res.append(s2[0]+s1+s2[1])\n",
    "\n",
    "            return res\n",
    "        else:\n",
    "            for i in range((n-2)//2):\n",
    "                if i != (n-2)//2-1:\n",
    "                    for s1 in n20:\n",
    "                        for s2 in n21:\n",
    "                            res.append(s2[0]+s1+s2[1])\n",
    "                    n20=res[:]\n",
    "                    res=[]\n",
    "                else:\n",
    "                    for s1 in n20:\n",
    "                        for s2 in n2:\n",
    "                            res.append(s2[0]+s1+s2[1])\n",
    "\n",
    "            return res\n",
    "\n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        pairs = [('1', '1'), ('8', '8'), ('6', '9'), ('9', '6')]\n",
    "        def back_tracking(x):\n",
    "            if x == 0:\n",
    "                return [\"\"]\n",
    "            if x == 1:\n",
    "                return ['0', '1', '8']\n",
    "            \n",
    "            ans = []\n",
    "            for num in back_tracking(x - 2):\n",
    "                for a, b in pairs:\n",
    "                    ans.append(a + num + b)\n",
    "                if x != n:\n",
    "                    ans.append('0' + num + '0')\n",
    "            return ans\n",
    "        return back_tracking(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def isStrobogrammatic(self, num: str) -> bool:\n",
    "        # 双指针解法\n",
    "        h_dict = {'0': '0', '1': '1', '6': '9', '8': '8', '9': '6'}\n",
    "        i, j = 0, len(num) - 1\n",
    "        while i <= j:\n",
    "            if num[i] not in h_dict or num[j] not in h_dict or h_dict[num[i]] != num[j] or h_dict[num[j]] != num[i]:\n",
    "                return False\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return True\n",
    "\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        # # 超出内存限制\n",
    "        # res = []\n",
    "        # nums = [str(i) for i in range(10 ** (n - 1), 10 ** n)]\n",
    "        # if n == 1: nums.insert(0, '0')\n",
    "        # for num in nums:\n",
    "        #     if self.isStrobogrammatic(num):\n",
    "        #         res.append(num)\n",
    "        # return res\n",
    "\n",
    "        # 回溯法\n",
    "        def helper(m, n):\n",
    "            if m == 0: return ['']\n",
    "            if m == 1: return ['0', '1', '8']\n",
    "            # 递归步骤，生成较小长度的中心对称数\n",
    "            middles = helper(m - 2, n)\n",
    "            result = []\n",
    "            for middle in middles:\n",
    "                # 对于不是最外层的中心对称数，可以在外侧加'0'\n",
    "                if m != n:\n",
    "                    result.append('0' + middle + '0')\n",
    "                # 添加其他中心对称数的组合\n",
    "                result.append('1' + middle + '1')\n",
    "                result.append('6' + middle + '9')\n",
    "                result.append('8' + middle + '8')\n",
    "                result.append('9' + middle + '6')\n",
    "            return result\n",
    "        # m：当前要生成的中心对称数的长度\n",
    "        # n：原始输入的长度，即最初的n。\n",
    "        return helper(n, n)\n",
    "\n",
    "        # # 回溯法\n",
    "        # def helper(left, right, tmp = [None] * n, res = tuple()):\n",
    "        #     if left > right: return (''.join(tmp), )\n",
    "        #     for k, v in (('0', '0'), ('1', '1'), ('6', '9'), ('8', '8'), ('9', '6')):\n",
    "        #         if not left and right and k == '0' or left == right and k != v: continue\n",
    "        #         tmp[left], tmp[right] = k, v\n",
    "        #         res += helper(left + 1, right - 1)\n",
    "        #     print(res)\n",
    "        #     return res\n",
    "        # return helper(0, n - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        odd = [\"0\", \"1\", \"8\"]\n",
    "        even = {\"1\": \"1\", \"6\": \"9\", \"8\": \"8\", \"9\": \"6\", \"0\": \"0\"}\n",
    "        res = []\n",
    "\n",
    "        def dfs(i: int, t: List[str]) -> None:\n",
    "            if i == n // 2:\n",
    "                if n % 2 == 0:\n",
    "                    res.append(\"\".join(t) + \"\".join(map(lambda x: even[x], t[::-1])))\n",
    "                else:\n",
    "                    for c in odd:\n",
    "                        res.append(\"\".join(t) + c + \"\".join(map(lambda x: even[x], t[::-1])))\n",
    "                return\n",
    "            for c in even:\n",
    "                if i == 0 and c == '0':\n",
    "                    continue\n",
    "                t.append(c)\n",
    "                dfs(i + 1, t)\n",
    "                t.pop()\n",
    "        dfs(0, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        if n == 1:\n",
    "            return [\"0\",\"1\",\"8\"]\n",
    "        rvsDict = {\"0\": \"0\", \"1\": \"1\", \"6\": \"9\", \"8\": \"8\", \"9\": \"6\"}\n",
    "        res = []\n",
    "        end = n // 2 + n % 2\n",
    "\n",
    "        def complete(s:str, keep_last: int):\n",
    "            idx = len(s) - 1 - keep_last\n",
    "            compRes = s\n",
    "            while idx >= 0:\n",
    "                compRes += rvsDict[s[idx]]\n",
    "                idx -= 1\n",
    "            return compRes\n",
    "\n",
    "        def backtrace(s:str,end:int, even: int):\n",
    "            if len(s) == end:\n",
    "                res.append(complete(s,n%2))\n",
    "                return\n",
    "            for key in rvsDict:\n",
    "                if len(s) == 0 and key == \"0\":\n",
    "                    continue\n",
    "                if not even and end - len(s) == 1:\n",
    "                    if key in [\"6\",\"9\"]:\n",
    "                        continue\n",
    "                s += key\n",
    "                backtrace(s,end,even)\n",
    "                s = s[:-1]\n",
    "        backtrace(\"\",end, 1-n%2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        map_dict = {'1':'1', '6': '9', '8': '8', '9': '6', '0': '0'}\n",
    "\n",
    "        if n == 1:\n",
    "            return ['1', '8', '0']\n",
    "\n",
    "        half_buffer = []\n",
    "        half_cnt = n // 2\n",
    "        result = []\n",
    "\n",
    "        def bt():\n",
    "            if len(half_buffer) == half_cnt:\n",
    "                if n % 2 == 0:\n",
    "                    temp_buffer = half_buffer + [map_dict[item] for item in half_buffer[:: -1]]\n",
    "                    result.append(''.join(temp_buffer))\n",
    "                else:\n",
    "                    for item in ['0', '8', '1']:\n",
    "                        temp_buffer = half_buffer + [item] + [map_dict[item] for item in half_buffer[:: -1]]\n",
    "                        result.append(''.join(temp_buffer))\n",
    "            else:\n",
    "                for item in map_dict:\n",
    "                    if item == '0' and not half_buffer:\n",
    "                        continue\n",
    "                    half_buffer.append(item)\n",
    "                    bt()\n",
    "                    half_buffer.pop()\n",
    "        bt()\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        d=('1','0','8')\n",
    "        a={'6':'9','0':'0','8':'8','9':'6','1':'1'}\n",
    "\n",
    "        res=[]\n",
    "        def backtrack(p,l,t):\n",
    "            if l==1:\n",
    "                for k in d:\n",
    "                    res.append(p+k+t)\n",
    "                return \n",
    "            \n",
    "            if l==0:\n",
    "                res.append(p+t)\n",
    "                return \n",
    "            \n",
    "            for k,v in a.items():\n",
    "                if not p and k=='0':\n",
    "                    continue\n",
    "                backtrack(p+k,l-2,v+t)\n",
    "        backtrack('',n,'')\n",
    "        return res\n",
    "    \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def findStrobogrammatic(self, n):\n",
    "        res = []\n",
    "        m = {'0': '0', '1': '1', '6': '9', '8': '8', '9': '6'}\n",
    "        def helper(left, right, tmp = [None] * n): # tmp 是可变对象，只会被初始化一次\n",
    "            if left > right:\n",
    "                res.append(\"\".join(tmp))\n",
    "                return\n",
    "            for k, v in m.items():\n",
    "                if not left and right and k == '0' or left == right and k != v: continue\n",
    "                tmp[left], tmp[right] = k, v\n",
    "                helper(left + 1, right - 1)\n",
    "        helper(0, n - 1)\n",
    "        return res\n",
    "\n",
    "### if的第二个条件，如果是奇数也可以操作，因为left==right的时候，0，1，8是符合条件\n",
    "### 这是一个数字，他的最左边和最右边都不能为0，就是第一次遍历的时候 即left==0的守候，不能用0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        d=('1','0','8')\n",
    "        a={'6':'9','0':'0','8':'8','9':'6','1':'1'}\n",
    "\n",
    "        res=[]\n",
    "\n",
    "\n",
    "        def backtrack(p,l,t):\n",
    "            if l==1:\n",
    "                for k in d:\n",
    "                    res.append(p+k+t[::-1])\n",
    "                return \n",
    "            \n",
    "            if l==0:\n",
    "                res.append(p+t[::-1])\n",
    "                return \n",
    "            \n",
    "            for k,v in a.items():\n",
    "                if not p and k=='0':\n",
    "                    continue\n",
    "                backtrack(p+k,l-2,t+v)\n",
    "        backtrack('',n,'')\n",
    "        return res\n",
    "    \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        result = list()\n",
    "        item = []\n",
    "        mid = [\"0\", \"1\", \"8\"]\n",
    "        all = [\"0\", \"1\", \"6\", \"8\", \"9\"]\n",
    "        lst = [\"1\", \"6\", \"8\", \"9\"]\n",
    "        dt = {\"1\": \"1\", \"0\": \"0\", \"6\": \"9\", \"9\": \"6\", \"8\": \"8\"}\n",
    "        def deal() -> str:\n",
    "            res = []\n",
    "            for i in item[n%2:]:\n",
    "                res.append(dt[i])\n",
    "            return \"\".join(res[::-1]) + \"\".join(item)\n",
    "\n",
    "        def traverse(items, remain):\n",
    "            if remain == 0:\n",
    "                one = deal()\n",
    "                result.append(one)\n",
    "                return\n",
    "            nextItems = lst if remain-1 == 1 else all\n",
    "            for i in items:\n",
    "                item.append(i)\n",
    "                traverse(nextItems, remain-1)\n",
    "                item.pop()\n",
    "\n",
    "        start = []\n",
    "        if n%2 == 1: start = mid\n",
    "        elif n == 2: start = lst\n",
    "        else: start = all\n",
    "\n",
    "        traverse(start, (n+1)//2)\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        d=('1','0','8')\n",
    "        a={'6':'9','0':'0','8':'8','9':'6','1':'1'}\n",
    "\n",
    "        res=[]\n",
    "\n",
    "\n",
    "        def backtrack(p,l,t):\n",
    "            if l==1:\n",
    "                for k in d:\n",
    "                    res.append(p+k+t[::-1])\n",
    "                return \n",
    "            \n",
    "            if l==0:\n",
    "                res.append(p+t[::-1])\n",
    "                return \n",
    "            \n",
    "            for k,v in a.items():\n",
    "                if not p and k=='0':\n",
    "                    continue\n",
    "                backtrack(p+k,l-2,t+v)\n",
    "        backtrack('',n,'')\n",
    "        return res\n",
    "    \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        d=('1','0','8')\n",
    "        a={'6':'9','0':'0','8':'8','9':'6','1':'1'}\n",
    "\n",
    "        res=[]\n",
    "        def backtrack(p,l,t):\n",
    "            if l==1:\n",
    "                for k in d:\n",
    "                    res.append(p+k+t)\n",
    "                return \n",
    "            \n",
    "            if l==0:\n",
    "                res.append(p+t)\n",
    "                return \n",
    "            \n",
    "            for k,v in a.items():\n",
    "                if not p and k=='0':\n",
    "                    continue\n",
    "                backtrack(p+k,l-2,v+t)\n",
    "        backtrack('',n,'')\n",
    "        return res\n",
    "    \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pair = {\n",
    "    '6':'9',\n",
    "    '9':'6',\n",
    "    '1':'1',\n",
    "    '8':'8',\n",
    "    '0':'0'\n",
    "}\n",
    "ones = '018'\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        ans, ele = [], [0 for _ in range(n)]\n",
    "        def dfs(l, r):\n",
    "            if l > r:\n",
    "                if n == 1 or ele[0] != '0':\n",
    "                    ans.append(''.join(ele))\n",
    "                return\n",
    "            if l == r:\n",
    "                for nex in ones:\n",
    "                    ele[l] = nex\n",
    "                    dfs(l + 1, r - 1)\n",
    "            else:\n",
    "                for k, v in pair.items():\n",
    "                    ele[l] = k\n",
    "                    ele[r] = v\n",
    "                    dfs(l + 1, r - 1)\n",
    "        \n",
    "        dfs(0, n - 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        symmetric = ['0', '1', '8']\n",
    "        rotary = {'0': '0', \n",
    "                  '1': '1', \n",
    "                  '6': '9',\n",
    "                  '8': '8', \n",
    "                  '9': '6'}\n",
    "        output = []\n",
    "        res = ''\n",
    "\n",
    "        def bfs(idx, w):\n",
    "            nonlocal res\n",
    "            if idx == w:\n",
    "                if not res.startswith('0'):\n",
    "                    output.append(res)\n",
    "                else:\n",
    "                    if len(res) == 1:\n",
    "                        output.append(res)\n",
    "                return \n",
    "            for num in rotary:\n",
    "                res = num + res + rotary[num]\n",
    "                bfs(idx+1, w)\n",
    "                res = res[1:-1]\n",
    "        \n",
    "        width = n // 2\n",
    "        if n % 2 == 1:\n",
    "            for i in symmetric:\n",
    "                res = i\n",
    "                bfs(0, width)\n",
    "        else:\n",
    "            bfs(0, width)\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        if n == 1:\n",
    "            return [\"0\", \"1\", \"8\"]\n",
    "        else:\n",
    "            m = {'0': '0', '1': '1', '6': '9', '8': '8', '9': '6'}\n",
    "            ans = []\n",
    "            path = [\" \"] * n \n",
    "            flag = True if n % 2 == 0 else False\n",
    "            def dfs(i, path):\n",
    "                if flag:\n",
    "                    if i == n // 2:\n",
    "                        ans.append(''.join(path))\n",
    "                        return \n",
    "                    if i == 0:\n",
    "                        for c in ['1', '6', '8', '9']:\n",
    "                            path[i] = c \n",
    "                            path[n-i-1] = m[c] \n",
    "                            dfs(i+1, path)\n",
    "                    else:\n",
    "                        for c in ['0', '1', '6', '8', '9']:\n",
    "                            path[i] = c \n",
    "                            path[n-i-1] = m[c] \n",
    "                            dfs(i+1, path)\n",
    "                else:\n",
    "                    if i == n // 2 + 1:\n",
    "                        ans.append(''.join(path))\n",
    "                        return \n",
    "                    if i == 0:\n",
    "                        for c in ['1', '6', '8', '9']:\n",
    "                            path[i] = c \n",
    "                            path[n-i-1] = m[c] \n",
    "                            dfs(i+1, path)\n",
    "                    elif i == n // 2:\n",
    "                        for c in ['0', '1', '8']:\n",
    "                            path[i] = c \n",
    "                            path[n-i-1] = m[c]\n",
    "                            dfs(i+1, path)\n",
    "                    else:\n",
    "                        for c in ['0', '1', '6', '8', '9']:\n",
    "                            path[i] = c \n",
    "                            path[n-i-1] = m[c]\n",
    "                            dfs(i+1, path)\n",
    "            dfs(0, path)\n",
    "            return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        flg = n % 2\n",
    "        tg = n // 2\n",
    "        # if flg == 0 else n // 2 + 1\n",
    "        ans = []\n",
    "\n",
    "        def pivot_180_degree(ss):\n",
    "            p180d = \"\"\n",
    "            for i in range(len(ss) - 1, -1, -1):\n",
    "                if ss[i] == '6':\n",
    "                    p180d += '9'\n",
    "                elif ss[i] == '9':\n",
    "                    p180d += '6'\n",
    "                else:\n",
    "                    p180d += ss[i]\n",
    "            return p180d\n",
    "\n",
    "        from functools import lru_cache\n",
    "        @lru_cache\n",
    "        def dfs(ss):\n",
    "            if len(ss) < tg:\n",
    "                for x in ['0', '1', '8', '6', '9']:\n",
    "                    if len(ss) == 0 and x == '0':\n",
    "                        pass\n",
    "                    else:\n",
    "                        dfs(ss + x)\n",
    "            elif len(ss) == tg:\n",
    "                nonlocal ans\n",
    "                if flg == 0:\n",
    "                    ans.append(ss + pivot_180_degree(ss))\n",
    "                else:\n",
    "                    ans.append(ss + '0' + pivot_180_degree(ss))\n",
    "                    ans.append(ss + '1' + pivot_180_degree(ss))\n",
    "                    ans.append(ss + '8' + pivot_180_degree(ss))\n",
    "\n",
    "        dfs(\"\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    reverseDict = {'0':'0', '1':'1', '6':'9', '8':'8', '9':'6'}\n",
    "    @lru_cache(None)\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        if not n:\n",
    "            return ['']\n",
    "        elif n == 1:\n",
    "            return ['0', '1', '8']\n",
    "        res = set()\n",
    "        for ans in self.findStrobogrammatic(n-2):\n",
    "            if n > 3:\n",
    "                res.add('10'+ ans[1:-1] + '01')\n",
    "                res.add('60' + ans[1:-1] + '09')\n",
    "                res.add('80' + ans[1:-1] + '08')\n",
    "                res.add('90' + ans[1:-1] + '06')\n",
    "            res.add('6' + ans + '9')\n",
    "            res.add('9' + ans + '6')\n",
    "            res.add('1' + ans + '1')\n",
    "            res.add('8' + ans + '8')\n",
    "        return list(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "#         dic={'0':'0', '1':'1', '6':'9', '8':'8', '9':'6'}\n",
    "\n",
    "\n",
    "\n",
    "# 作者：Benhao\n",
    "# 链接：https://leetcode.cn/problems/strobogrammatic-number-ii/\n",
    "class Solution:\n",
    "    reverseDict = {'0':'0', '1':'1', '6':'9', '8':'8', '9':'6'}\n",
    "    @lru_cache(None)\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        if not n:\n",
    "            return ['']\n",
    "        elif n == 1:\n",
    "            return ['0', '1', '8']\n",
    "        res = set()\n",
    "        for ans in self.findStrobogrammatic(n-2):\n",
    "            if n > 3:\n",
    "                res.add('10'+ ans[1:-1] + '01')\n",
    "                res.add('60' + ans[1:-1] + '09')\n",
    "                res.add('80' + ans[1:-1] + '08')\n",
    "                res.add('90' + ans[1:-1] + '06')\n",
    "            res.add('6' + ans + '9')\n",
    "            res.add('9' + ans + '6')\n",
    "            res.add('1' + ans + '1')\n",
    "            res.add('8' + ans + '8')\n",
    "        return list(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        # reverse_dict = {'0': '0', '1': '1', '6':'9'}\n",
    "        if not n:\n",
    "            return ['']\n",
    "        elif n == 1:\n",
    "            return [\"0\",\"1\",\"8\"]\n",
    "        # if n == 2:\n",
    "        #     return [\"11\",\"69\",\"88\",\"96\"]\n",
    "        \n",
    "        res = set()\n",
    "        for x in self.findStrobogrammatic(n-2):\n",
    "            if n > 3:\n",
    "                res.add('10' + x[1:-1] + '01')\n",
    "                res.add('60' + x[1:-1] + '09')\n",
    "                res.add('90' + x[1:-1] + '06')\n",
    "                res.add('80' + x[1:-1] + '08')\n",
    "            res.add('6' + x + '9')\n",
    "            res.add('8' + x + '8')\n",
    "            res.add('1' + x + '1')\n",
    "            res.add('9' + x + '6')\n",
    "            \n",
    "        return list(res)\n",
    "                \n",
    "                \n",
    "            \n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        @cache\n",
    "        def func(n):\n",
    "            if n < 0:\n",
    "                return []\n",
    "            elif n == 0:\n",
    "                return ['']\n",
    "            elif n == 1:\n",
    "                return ['0', '1', '8']\n",
    "            \n",
    "            ret = []\n",
    "            for nzero in range(0, n-1, 2):\n",
    "                for s in func(n-2-nzero):\n",
    "                    for prefix, suffix in [('1','1'), ('6','9'), ('8','8'), ('9','6')]:\n",
    "                        ret.append(prefix + '0'*(nzero//2) + s + '0'*(nzero//2) + suffix)\n",
    "            return ret\n",
    "    \n",
    "        return func(n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        @cache\n",
    "        def func(n):\n",
    "            if n == 0:\n",
    "                return ['']\n",
    "            elif n == 1:\n",
    "                return ['0', '1', '8']\n",
    "            \n",
    "            ret = []\n",
    "            for nzero in range(0, n-1, 2):\n",
    "                for s in func(n-2-nzero):\n",
    "                    for prefix, suffix in [('1','1'), ('6','9'), ('8','8'), ('9','6')]:\n",
    "                        ret.append(prefix + '0'*(nzero//2) + s + '0'*(nzero//2) + suffix)\n",
    "            return ret\n",
    "    \n",
    "        return func(n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        @cache\n",
    "        def func(n):\n",
    "            if n == 0:\n",
    "                return ['']\n",
    "            elif n == 1:\n",
    "                return ['0', '1', '8']\n",
    "            \n",
    "            ret = []\n",
    "            for nzero in range(0, n-1, 2):\n",
    "                zstr = '0'*(nzero//2)\n",
    "                for s in func(n-2-nzero):\n",
    "                    for prefix, suffix in [('1','1'), ('6','9'), ('8','8'), ('9','6')]:\n",
    "                        ret.append(prefix + zstr + s + zstr + suffix)\n",
    "            return ret\n",
    "    \n",
    "        return func(n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        @cache\n",
    "        def func(n):\n",
    "            if n < 0:\n",
    "                return []\n",
    "            elif n == 0:\n",
    "                return ['']\n",
    "            elif n == 1:\n",
    "                return ['0', '1', '8']\n",
    "            elif n == 2:\n",
    "                return [\"11\",\"69\",\"88\",\"96\"]\n",
    "            \n",
    "            ret = []\n",
    "            for nzero in range(0, n-1, 2):\n",
    "                for s in func(n-2-nzero):\n",
    "                    for prefix, suffix in [('1','1'), ('6','9'), ('8','8'), ('9','6')]:\n",
    "                        ret.append(prefix + '0'*(nzero//2) + s + '0'*(nzero//2) + suffix)\n",
    "            return ret\n",
    "    \n",
    "        return func(n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        @cache\n",
    "        def func(n):\n",
    "            if n < 0:\n",
    "                return []\n",
    "            elif n == 0:\n",
    "                return ['']\n",
    "            elif n == 1:\n",
    "                return ['0', '1', '8']\n",
    "            elif n == 2:\n",
    "                return [\"11\",\"69\",\"88\",\"96\"]\n",
    "            \n",
    "            ret = []\n",
    "            for nzero in range(0, n-1, 2):\n",
    "                for s in func(n-2-nzero):\n",
    "                    for prefix, suffix in [('1','1'), ('6','9'), ('8','8'), ('9','6')]:\n",
    "                        ret.append(prefix + '0'*(nzero//2) + s + '0'*(nzero//2) + suffix)\n",
    "            return ret\n",
    "    \n",
    "        return func(n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.m= {\"1\":\"1\", \"6\":\"9\",\"9\":\"6\", \"8\":\"8\",\"0\":\"0\"}\n",
    "\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        res=[]\n",
    "\n",
    "        L_left=[]\n",
    "        self.gen_left(n//2, \"\", L_left)\n",
    "        \n",
    "        if n%2==0:\n",
    "            mids=[\"\"]\n",
    "        else:\n",
    "            mids=[\"0\",\"1\",\"8\"]\n",
    "\n",
    "        for mid in mids:\n",
    "            for left in L_left:\n",
    "                res.append(left + mid + \"\".join([self.m.get(ch) for ch in left[::-1]]))\n",
    "        return [ ele for ele in res if len(ele) == len(str(int(ele)))]\n",
    "        \n",
    "\n",
    "    \n",
    "    def gen_left(self, n, s, res):\n",
    "        if n==0:\n",
    "            res.append(s)\n",
    "            return\n",
    "\n",
    "        for ch in self.m.keys():\n",
    "            self.gen_left(n-1, s+ch, res)\n",
    "        \n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        one_sym=[0,1,8]\n",
    "        ret=[]\n",
    "        #two_sym 6,9\n",
    "        def f(s):\n",
    "            if len(s)==n:\n",
    "                ret.append(s)\n",
    "                return\n",
    "            if s=='':\n",
    "                if n%2==1:\n",
    "                    for item in one_sym:\n",
    "                        f(str(item))\n",
    "                else:\n",
    "                    for item in one_sym:\n",
    "                        f(str(item)+s+str(item))\n",
    "                    f('6'+s+'9')\n",
    "                    f('9'+s+'6')\n",
    "            else:\n",
    "                for item in one_sym:\n",
    "                    f(str(item)+s+str(item))\n",
    "                f('6'+s+'9')\n",
    "                f('9'+s+'6')\n",
    "        f('')\n",
    "        real_ret=[]\n",
    "        for i in ret:\n",
    "            if i[0]!='0' or len(i)==1:\n",
    "                real_ret.append(i)\n",
    "        return real_ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        one_sym=[0,1,8]\n",
    "        ret=[]\n",
    "        #two_sym 6,9\n",
    "        def f(s):\n",
    "            if len(s)==n:\n",
    "                ret.append(s)\n",
    "                return\n",
    "            if s=='':\n",
    "                if n%2==1:\n",
    "                    for item in one_sym:\n",
    "                        f(str(item))\n",
    "                else:\n",
    "                    for item in one_sym:\n",
    "                        f(str(item)+s+str(item))\n",
    "                    f('6'+s+'9')\n",
    "                    f('9'+s+'6')\n",
    "            else:\n",
    "                for item in one_sym:\n",
    "                    f(str(item)+s+str(item))\n",
    "                f('6'+s+'9')\n",
    "                f('9'+s+'6')\n",
    "        f('')\n",
    "        real_ret=[]\n",
    "        for i in ret:\n",
    "            if i[0]!='0' or len(i)==1:\n",
    "                real_ret.append(i)\n",
    "        return real_ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        res = []\n",
    "        tmp = [None] * n\n",
    "\n",
    "        def dfs(i):\n",
    "            j = n - 1 - i\n",
    "            if i == j:\n",
    "                for char in \"018\":\n",
    "                    tmp[i] = char\n",
    "                    res.append(\"\".join(tmp))\n",
    "                return\n",
    "\n",
    "            if i == j - 1:\n",
    "                for char in \"018\":\n",
    "                    tmp[i] = tmp[j] = char\n",
    "                    res.append(\"\".join(tmp))\n",
    "\n",
    "                for x, y in zip(\"69\", \"96\"):\n",
    "                    tmp[i] = x\n",
    "                    tmp[j] = y\n",
    "                    res.append(\"\".join(tmp))\n",
    "\n",
    "                return\n",
    "\n",
    "            for char in \"018\":\n",
    "                tmp[i] = tmp[j] = char\n",
    "                dfs(i + 1)\n",
    "\n",
    "            for x, y in zip(\"69\", \"96\"):\n",
    "                tmp[i] = x\n",
    "                tmp[j] = y\n",
    "                dfs(i + 1)\n",
    "\n",
    "        dfs(0)\n",
    "        return [x for x in res if len(x) == 1 or x[0] != \"0\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "each = ['6', '9']\n",
    "single = ['0', '1', '8']\n",
    "h = {'1': '1', '0': '0', '8': '8', '6': '9', '9': '6'}\n",
    "d = [[] for _ in range(8)]\n",
    "d[1] = ['1', '6', '8', '9']\n",
    "for i in range(2, 8):\n",
    "    for pre in d[i - 1]:\n",
    "        for j in ['0', '1', '8', '6', '9']:\n",
    "            d[i].append(pre + j)\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        if n == 1:\n",
    "            return [\"0\",\"1\",\"8\"]\n",
    "        if n == 2:\n",
    "            return [\"11\",\"69\",\"88\",\"96\"]\n",
    "        ans = []\n",
    "        \n",
    "        def f(x):\n",
    "            y = x[::-1]\n",
    "            res = ''\n",
    "            for i in y:\n",
    "                res += h[i]\n",
    "            return res \n",
    "        \n",
    "        if n % 2:\n",
    "            for i in d[(n - 1) // 2]:\n",
    "                for j in single:\n",
    "                    tmp = i + j + f(i)\n",
    "                    ans.append(tmp)\n",
    "        else:\n",
    "            for i in d[n // 2]:\n",
    "                tmp = i + f(i)\n",
    "                ans.append(tmp)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        mid=['0','1','8']\n",
    "        at=['1','6','8','9','0']\n",
    "        dt=dict()\n",
    "        dt['1']='1'\n",
    "        dt['8']='8'\n",
    "        dt['9']='6'\n",
    "        dt['6']='9'\n",
    "        dt['0']='0'\n",
    "        def g(temp):\n",
    "            if len(temp)==target:\n",
    "                left.append(temp)\n",
    "                return \n",
    "            for j in at:\n",
    "                if len(temp)==0 and j=='0':\n",
    "                    continue\n",
    "                g(temp+j)\n",
    "        def un(x,y):\n",
    "            z=''\n",
    "            for i in x[::-1]:\n",
    "                z=z+dt[i]\n",
    "                \n",
    "            return x+y+z\n",
    "        if n==1:\n",
    "            return mid\n",
    "        left=[]\n",
    "        target=n//2\n",
    "        g('')\n",
    "        print(left)\n",
    "        ans=[]\n",
    "        if n%2==1:\n",
    "            for tt in left:\n",
    "                for jj in mid:\n",
    "                    ans.append(un(tt,jj))\n",
    "        else:\n",
    "            for tt in left:\n",
    "                ans.append(un(tt,''))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        nums = {\n",
    "            '0': '0',\n",
    "            '1': '1',\n",
    "            '6': '9',\n",
    "            '8': '8',\n",
    "            '9': '6',\n",
    "        }\n",
    "        good = {'0', '1', '8'}\n",
    "        m = n // 2\n",
    "        ans = []\n",
    "\n",
    "        def backtrack(path):\n",
    "            if len(path) == m:\n",
    "                ans.append(path)\n",
    "                return\n",
    "            \n",
    "            for num in nums:\n",
    "                if not path and num == '0':\n",
    "                    continue\n",
    "                backtrack(path + [num])\n",
    "        \n",
    "        backtrack([])\n",
    "        final_ans = []\n",
    "        for path in ans:\n",
    "            # is_good = n > 1 and all([ch in good for ch in path])\n",
    "            reverse = [nums[ch] for ch in path]\n",
    "            # print(n, is_good)\n",
    "            if n % 2 == 1:\n",
    "                for good_num in good:\n",
    "                    final_ans.append(''.join(path) + good_num + ''.join(reverse[::-1]))\n",
    "            else:\n",
    "                final_ans.append(''.join(path) + ''.join(reverse[::-1]))\n",
    "\n",
    "        return final_ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        map_dict = {'1':'1', '6': '9', '8': '8', '9': '6', '0': '0'}\n",
    "        candidates = ['0', '1', '6', '8', '9']\n",
    "        head_candidates = ['1', '6', '8', '9']\n",
    "        sames = ['0', '1', '8']\n",
    "\n",
    "        buffer = []\n",
    "        ret_list = []\n",
    "\n",
    "        def bt():\n",
    "            if n % 2 == 0:\n",
    "                if len(buffer) == n // 2:\n",
    "                    ret_list.append(buffer[:])\n",
    "                    return\n",
    "                else:\n",
    "                    if not buffer:\n",
    "                        for item in head_candidates:\n",
    "                            buffer.append(item)\n",
    "                            bt()\n",
    "                            buffer.pop()\n",
    "                    else:\n",
    "                        for item in candidates:\n",
    "                            buffer.append(item)\n",
    "                            bt()\n",
    "                            buffer.pop()\n",
    "\n",
    "            else:\n",
    "                if len(buffer) == n // 2 + 1:\n",
    "                    ret_list.append(buffer[:])\n",
    "                    return\n",
    "                elif len(buffer) == n // 2:\n",
    "                    for item in sames:\n",
    "                        buffer.append(item)\n",
    "                        bt()\n",
    "                        buffer.pop()\n",
    "                else:\n",
    "                    if not buffer:\n",
    "                        for item in head_candidates:\n",
    "                            buffer.append(item)\n",
    "                            bt()\n",
    "                            buffer.pop()\n",
    "                    else:\n",
    "                        for item in candidates:\n",
    "                            buffer.append(item)\n",
    "                            bt()\n",
    "                            buffer.pop()\n",
    "        bt()\n",
    "        def convert_odd(input_buffer):\n",
    "            pre_list = input_buffer[: -1]\n",
    "            temp = [map_dict[item] for item in pre_list][:: -1]\n",
    "            return ''.join(input_buffer + temp)\n",
    "        def convert_even(input_buffer):\n",
    "            temp = [map_dict[item] for item in input_buffer][:: -1]\n",
    "            return ''.join(input_buffer + temp)\n",
    "        if n % 2 == 0:\n",
    "            return [convert_even(item) for item in ret_list]\n",
    "        else:\n",
    "            return [convert_odd(item) for item in ret_list]\n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        if True:\n",
    "            num_mappings = {\"0\":\"0\", \"1\":\"1\", \"6\":\"9\", \"8\":\"8\", \"9\":\"6\"}\n",
    "            left_nums = \"01689\"\n",
    "            central_nums = \"018\"\n",
    "            if n ==0: return []\n",
    "            if n ==1: return list(central_nums)\n",
    "            half_nums = []\n",
    "            def dfs(paths):\n",
    "                if len(paths) == n//2:\n",
    "                    half_nums.append(paths)\n",
    "                    return\n",
    "                for i, num in enumerate(left_nums):\n",
    "                    dfs(paths+[num])\n",
    "            dfs([])\n",
    "            print(list(half_nums))\n",
    "            if n%2==0:\n",
    "                results = [\"\".join(list(i) + [num_mappings[j] for j in i][::-1]) for i in half_nums]\n",
    "            else:\n",
    "                results = [\"\".join(list(i) + [j] + [num_mappings[j] for j in i][::-1]) for i in half_nums for j in central_nums]\n",
    "            results = [i for i in results if str(int(i)) == i]            \n",
    "            print(results)\n",
    "            return results\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        if False:\n",
    "            c_map = {\"0\":\"0\", \"1\":\"1\", \"6\":\"9\", \"8\":\"8\", \"9\":\"6\"}\n",
    "            if n==0: return []\n",
    "            if n == 1: return [\"0\",\"1\", \"8\"]\n",
    "            \n",
    "            results = []\n",
    "            def dfs(paths):\n",
    "                if len(paths) == n//2:\n",
    "                    results.append(paths+[c_map[i] for i in paths[::-1]])\n",
    "                    return\n",
    "                if len(paths)>n//2:\n",
    "                    return\n",
    "                for i in range(len(c_map)):\n",
    "                    dfs(paths + [list(c_map.keys())[i]])\n",
    "            dfs([])\n",
    "\n",
    "            if n%2: results = [j[:n//2] + [str(i)] + j[n//2:] for j in results for i in [\"0\", \"1\", \"8\"]]\n",
    "            results = [\"\".join(i) for i in results]\n",
    "            results = [i for i in results if i == str(int(i))]\n",
    "            return results\n",
    "\n",
    "            \n",
    "                \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        c_map = {\"0\":\"0\", \"1\":\"1\", \"6\":\"9\", \"8\":\"8\", \"9\":\"6\"}\n",
    "        if n==0: return []\n",
    "        if n == 1: return [\"0\",\"1\", \"8\"]\n",
    "        \n",
    "        results = []\n",
    "        def dfs(paths):\n",
    "            if len(paths) == n//2:\n",
    "                results.append(paths+[c_map[i] for i in paths[::-1]])\n",
    "                return\n",
    "            if len(paths)>n//2:\n",
    "                return\n",
    "            for i in range(len(c_map)):\n",
    "                dfs(paths + [list(c_map.keys())[i]])\n",
    "        dfs([])\n",
    "\n",
    "        if n%2: results = [j[:n//2] + [str(i)] + j[n//2:] for j in results for i in [\"0\", \"1\", \"8\"]]\n",
    "        results = [\"\".join(i) for i in results]\n",
    "        results = [i for i in results if i == str(int(i))]\n",
    "        return results\n",
    "\n",
    "            \n",
    "                \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        chars = ['0', '1', '6', '8', '9']\n",
    "        record = {'0': '0', '1': '1', '6': '9', '8': '8', '9': '6'}\n",
    "        temp = []\n",
    "\n",
    "        def dfs(index, cur1, cur2):\n",
    "            if index == n//2:\n",
    "                temp.append([cur1, cur2])\n",
    "                return\n",
    "            for c in chars:\n",
    "                if index == 0 and c == '0':\n",
    "                    continue\n",
    "                dfs(index+1, cur1+c, cur2+record[c])\n",
    "        \n",
    "        dfs(0, '', '')\n",
    "        res = []\n",
    "        if n%2 == 0:\n",
    "             for char1, char2 in temp:\n",
    "                 res.append(char1+char2[::-1])\n",
    "        else:\n",
    "            for char1, char2 in temp:\n",
    "                res.append(char1+'0'+char2[::-1])\n",
    "                res.append(char1+'1'+char2[::-1])\n",
    "                res.append(char1+'8'+char2[::-1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findStrobogrammatic(self, n: int) -> List[str]:\n",
    "        if n==1:\n",
    "            return ['0','1','8']\n",
    "        ans = []\n",
    "        def backtrack(last,remain):\n",
    "            if remain>0:\n",
    "                for i in '0','1','6','8','9':\n",
    "                    backtrack(last+i, remain-1)\n",
    "            else:\n",
    "                nonlocal ans\n",
    "                ans.append(last)\n",
    "        backtrack('', (n+1)//2)\n",
    "        if n%2==0:\n",
    "            return [x+x.replace('9', 'x').replace('6', '9').replace('x', '6')[::-1] for x in ans if x[0]!='0']\n",
    "        return [x+x[:-1].replace('9', 'x').replace('6', '9').replace('x', '6')[::-1] for x in ans if x[-1]!='6' and x[-1]!='9' and x[0]!='0']"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
